package bintree.nowcoder;

/**
 * @Author: yuisama
 * @Date: 2021/9/8 18:06
 * @Description:ADT转换为双向链表
 * https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
 */
public class ConvertTree {
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 若空树返回空；只有根节点的树，直接返回根节点
        if (pRootOfTree == null)
            return null;
        if (pRootOfTree.left == null && pRootOfTree.right == null)
            return pRootOfTree;
        // 先递归处理左子树
        // 此时左子树已经是一个排序好的双向链表，left指向链表头，需要找到链表尾部与root连接
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode leftTail = left;
        while (leftTail != null && leftTail.right != null)
            leftTail = leftTail.right;
        // 此时leftTail指向左树链表尾部,将leftTail与根节点连接
        if (left != null) {
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        // 再递归处理右子树
        TreeNode right = Convert(pRootOfTree.right);
        // 此时右子树已经是一个排序好的双向链表，right指向链表头，找到右侧子树的尾部，与左侧链表头相连
        TreeNode rightTail = right;
        // 连接根节点与右侧链表头
        if (right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left == null ? pRootOfTree : left;
    }
}
